Схема Эль-Гамаля

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1985 году.^[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA, алгоритм Эль-Гамаля не был запатентован и поэтому стал более дешёвой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Генерация ключей

Генерируется случайное простое число [math]\displaystyle{ p }[/math].
Выбирается целое число [math]\displaystyle{ g }[/math] — первообразный корень [math]\displaystyle{ p }[/math].
Выбирается случайное целое число [math]\displaystyle{ x }[/math] такое, что [math]\displaystyle{ (1 \lt x \lt p - 1) }[/math].
Вычисляется [math]\displaystyle{ y = g^x \bmod p }[/math].
Открытым ключом является [math]\displaystyle{ (y,g,p) }[/math], закрытым ключом — число [math]\displaystyle{ x }[/math].

Работа в режиме шифрования

Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана.^{[источник не указан 898 дней]} Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Шифрование

Сообщение [math]\displaystyle{ M }[/math] должно быть меньше числа [math]\displaystyle{ p }[/math]. Сообщение шифруется следующим образом:

Выбирается сессионный ключ — случайное целое число, взаимно простое с [math]\displaystyle{ (p - 1) }[/math], [math]\displaystyle{ k }[/math] такое, что [math]\displaystyle{ 1 \lt k \lt p - 1 }[/math].
Вычисляются числа [math]\displaystyle{ a = g^k \bmod p }[/math] и [math]\displaystyle{ b = y^k M \bmod p }[/math].
Пара чисел [math]\displaystyle{ (a,b) }[/math] является шифротекстом.

Нетрудно заметить, что длина шифротекста в схеме Эль-Гамаля вдвое больше исходного сообщения [math]\displaystyle{ M }[/math].

Расшифрование

Зная закрытый ключ [math]\displaystyle{ x }[/math], исходное сообщение можно вычислить из шифротекста [math]\displaystyle{ (a,b) }[/math] по формуле:

[math]\displaystyle{ M = b(a^x)^{-1} \bmod p. }[/math]

При этом нетрудно проверить, что

[math]\displaystyle{ (a^x)^{-1} = g^{-kx} \bmod p }[/math]

и поэтому

[math]\displaystyle{ b(a^x)^{-1} = (y^kM)g^{-xk}\equiv (g^{xk}M) g^{-xk}\equiv M \pmod{p} }[/math].

Для практических вычислений больше подходит следующая формула:

[math]\displaystyle{ M = b(a^x)^{-1} = b a^{(p-1-x)} \pmod{p} }[/math]

Схема шифрования

Пример

Шифрование
1. Допустим, что нужно зашифровать сообщение [math]\displaystyle{ M=5 }[/math].
2. Произведем генерацию ключей:
  1. Пусть [math]\displaystyle{ p=11, g=2 }[/math]. Выберем [math]\displaystyle{ x=8 }[/math] - случайное целое число [math]\displaystyle{ x }[/math] такое,что [math]\displaystyle{ 1 \lt x \lt p }[/math].
  2. Вычислим [math]\displaystyle{ y= g^x\bmod{p}=2^8\bmod{11}=3 }[/math].
  3. Итак, открытым ключом является тройка [math]\displaystyle{ (p,g,y)=(11,2,3) }[/math],а закрытым ключом - число [math]\displaystyle{ x=8 }[/math].
3. Выбираем случайное целое число [math]\displaystyle{ k }[/math] такое, что 1 < k < (p − 1). Пусть [math]\displaystyle{ k=9 }[/math].
4. Вычисляем число [math]\displaystyle{ a=g^k\bmod{p}=2^9 \bmod{11}=512 \bmod{11}=6 }[/math].
5. Вычисляем число [math]\displaystyle{ b=y^k M\bmod{p}=3^9 5 \bmod{11}=19683 \cdot 5 \bmod{11}=9 }[/math].
6. Полученная пара [math]\displaystyle{ (a,b)=(6,9) }[/math] является шифротекстом.
Расшифрование
1. Необходимо получить сообщение [math]\displaystyle{ M=5 }[/math] по известному шифротексту [math]\displaystyle{ (a,b)=(6,9) }[/math] и закрытому ключу [math]\displaystyle{ x=8 }[/math].
2. Вычисляем M по формуле: [math]\displaystyle{ M=b(a^x)^{-1}\bmod{p}=9(6^8)^{-1}\mod{11}=5 }[/math]
3. Получили исходное сообщение [math]\displaystyle{ M=5 }[/math].

Так как в схему Эль-Гамаля вводится случайная величина [math]\displaystyle{ k }[/math],то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа [math]\displaystyle{ k }[/math] такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение [math]\displaystyle{ M }[/math] и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины [math]\displaystyle{ k }[/math] для шифровки различных сообщений [math]\displaystyle{ M }[/math] и [math]\displaystyle{ M' }[/math]. Если использовать одинаковые [math]\displaystyle{ k }[/math], то для соответствующих шифротекстов [math]\displaystyle{ (a,b) }[/math] и [math]\displaystyle{ (a',b') }[/math] выполняется соотношение [math]\displaystyle{ b(b')^{-1}=M(M')^{-1} }[/math]. Из этого выражения можно легко вычислить [math]\displaystyle{ M' }[/math], если известно [math]\displaystyle{ M }[/math].

Работа в режиме подписи

Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции [math]\displaystyle{ h(\cdot) }[/math], значения которой лежат в интервале [math]\displaystyle{ \left( 1, p - 1 \right) }[/math].

Подпись сообщений

Для подписи сообщения [math]\displaystyle{ M }[/math] выполняются следующие операции:

Вычисляется дайджест сообщения [math]\displaystyle{ M }[/math]: [math]\displaystyle{ m = h(M). }[/math](Хеш функция может быть любая).
Выбирается случайное число [math]\displaystyle{ 1\lt k \lt p-1 }[/math] взаимно простое с [math]\displaystyle{ p - 1 }[/math] и вычисляется [math]\displaystyle{ r = g^k\,\bmod\,p. }[/math]
Вычисляется число [math]\displaystyle{ s \, = \, (m-x r)k^{-1} \pmod{p-1} }[/math], где [math]\displaystyle{ k^{-1} }[/math] это мультипликативное обратное [math]\displaystyle{ k }[/math] по модулю [math]\displaystyle{ p - 1 }[/math], которое можно найти, например, с помощью расширенного алгоритма Евклида.
Подписью сообщения [math]\displaystyle{ M }[/math] является пара [math]\displaystyle{ \left( r,s \right) }[/math].

Проверка подписи

Зная открытый ключ [math]\displaystyle{ \left( p,g,y \right) }[/math], подпись [math]\displaystyle{ \left( r,s \right) }[/math] сообщения [math]\displaystyle{ M }[/math] проверяется следующим образом:

Проверяется выполнимость условий: [math]\displaystyle{ 0\lt r\lt p }[/math] и [math]\displaystyle{ 0\lt s\lt p-1 }[/math].
Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется дайджест [math]\displaystyle{ m = h(M). }[/math]
Подпись считается верной, если выполняется сравнение:
[math]\displaystyle{ y^r r^s \equiv g^m \pmod{p}. }[/math]

Корректность проверки

Рассматриваемый алгоритм корректен в том смысле, что подпись, вычисленная по указанным выше правилам, будет принята при ее проверке.

Преобразуя определение [math]\displaystyle{ s }[/math], имеем

[math]\displaystyle{ m \, \equiv \, x r + s k \pmod{p-1}. }[/math]

Далее, из Малой теоремы Ферма следует, что

[math]\displaystyle{ \begin{align} g^{m} & \equiv g^{xr} g^{ks} \\ & \equiv (g^{x})^r (g^{k})^s \\ & \equiv (y)^r (r)^s \pmod p.\\ \end{align} }[/math]

Пример

Подпись сообщения.
1. Допустим,что нужно подписать сообщение [math]\displaystyle{ M=baaqab }[/math].
2. Произведем генерацию ключей:
  1. Пусть [math]\displaystyle{ p=23 }[/math] [math]\displaystyle{ g=5 }[/math] переменные, которые известны некоторому сообществу.
  2. Секретный ключ [math]\displaystyle{ x=7 }[/math] — случайное целое число [math]\displaystyle{ x }[/math] такое, что [math]\displaystyle{ 1 \lt x \lt p }[/math].
  3. Вычисляем открытый ключ [math]\displaystyle{ y }[/math]: [math]\displaystyle{ y=g^x\bmod p=5^7 \bmod 23=17 }[/math].
  4. Итак,открытым ключом является тройка [math]\displaystyle{ (p,g,y)=(23,5,17) }[/math].
3. Теперь вычисляем хеш-функцию: [math]\displaystyle{ h(M)=h(baaqab)=m=3 }[/math].
4. Выберем случайное целое число [math]\displaystyle{ k }[/math] такое, что выполняется условие [math]\displaystyle{ 1 \lt k \lt p-1 }[/math]. Пусть [math]\displaystyle{ k=5 }[/math].
5. Вычисляем r = g^k mod p = 5^5 mod 23 = 20.
6. Находим [math]\displaystyle{ k^{-1} }[/math]. Такое число существует, так как НОД[math]\displaystyle{ (k, p-1)=1 }[/math]. Его можно найти с помощью расширенного алгоритма Евклида. Получим [math]\displaystyle{ k^{-1} = 5^{-1} \pmod{22} = 9 }[/math]
7. Находим число [math]\displaystyle{ s \, \equiv \, (m-x r)k^{-1} \pmod{p-1} }[/math]. Получим [math]\displaystyle{ s=21 }[/math], так как [math]\displaystyle{ s = \, (3 - 7 \cdot 20)5^{-1} \pmod{22} = 21 }[/math]
8. Итак, мы подписали сообщение: [math]\displaystyle{ \lt baaqab,20,21\gt }[/math].

Проверка подлинности полученного сообщения.
1. Вычисляем хеш-функцию: [math]\displaystyle{ h(M)=h(baaqab)=m=3 }[/math].
2. Проверяем сравнение [math]\displaystyle{ y^r \cdot r^s\pmod{p} \equiv g^m \pmod{p} }[/math].
3. Вычислим левую часть по модулю 23: [math]\displaystyle{ 17^{20} \cdot 20^{21} \bmod 23=16 \cdot 15 \bmod 23=10 }[/math].
4. Вычислим правую часть по модулю 23: [math]\displaystyle{ 5^3\bmod 23=10 }[/math].
5. Так как правая и левая части равны, то это означает что подпись верна.

Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле [math]\displaystyle{ \mathbb{Z}_p }[/math]. Следует сделать несколько комментариев:

Случайное число [math]\displaystyle{ k }[/math] должно сразу после вычисления подписи уничтожаться, так как если злоумышленник знает случайное число [math]\displaystyle{ k }[/math] и саму подпись, то он легко может найти секретный ключ по формуле: [math]\displaystyle{ x=(m-ks)r^{-1} \bmod (p-1) }[/math] и полностью подделать подпись.

Число [math]\displaystyle{ k }[/math] должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.

Использование свертки [math]\displaystyle{ m=h(M) }[/math] объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа [math]\displaystyle{ i,j }[/math],удовлетворяющие условиям [math]\displaystyle{ 0\lt i\lt {p-1} , 0\lt j\lt {p-1} }[/math], НОД(j,p-1)=1 и предположить что
[math]\displaystyle{ r=g^i \cdot y^{-j} \bmod p }[/math]

[math]\displaystyle{ s=r \cdot j^{-1} \bmod (p-1) }[/math]

[math]\displaystyle{ m=r \cdot i \cdot j^{-1} \bmod (p-1) }[/math]

то легко удостовериться в том,что пара [math]\displaystyle{ (r,s) }[/math] является верной цифровой подписью для сообщения [math]\displaystyle{ x=M }[/math].

Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: [math]\displaystyle{ y^A \cdot r^B=g^C(modp) }[/math], в котором тройка [math]\displaystyle{ (A,B,C) }[/math] принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при [math]\displaystyle{ A=r }[/math], [math]\displaystyle{ B=s }[/math], [math]\displaystyle{ C=m }[/math].На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения [math]\displaystyle{ A=r }[/math], [math]\displaystyle{ B=-s }[/math], [math]\displaystyle{ C=m }[/math], а в Российском стандарте: [math]\displaystyle{ A=-x }[/math], [math]\displaystyle{ B=-m }[/math], [math]\displaystyle{ C=s }[/math].
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел [math]\displaystyle{ (s,m) }[/math] на пару чисел [math]\displaystyle{ (s \bmod q,m \bmod q }[/math]),где [math]\displaystyle{ q }[/math] является каким-то простым делителем числа [math]\displaystyle{ (p-1) }[/math]. При этом сравнение для проверки подписи по модулю [math]\displaystyle{ p }[/math] нужно заменить на новое сравнение по модулю [math]\displaystyle{ q }[/math]: [math]\displaystyle{ (~y^A \cdot r^B) \bmod p = g^C \pmod{q} }[/math]. Так сделано в американском стандарте DSS (Digital Signature Standard).

Криптостойкость и особенности

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

[math]\displaystyle{ y \equiv g^x\pmod{p}. }[/math]

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

Сравнение некоторых алгоритмов:

Алгоритм	Ключ	Назначение	Криптостойкость, MIPS	Примечания
RSA	До 4096 бит	Шифрование и подпись	2,7•10²⁸ для ключа 1300 бит	Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
ElGamal	До 4096 бит	Шифрование и подпись	При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•10²⁸ для ключа 1300 бит	Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
DSA	До 1024 бит	Только подпись		Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
ECDSA	До 4096 бит	Шифрование и подпись	Криптостойкость и скорость работы выше, чем у RSA	Современное направление. Разрабатывается многими ведущими математиками

Примечания

↑ Elgamal, 1985.

Литература

Шаблон:Source
Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии.^{[уточнить]}
Б. А. Фороузан. Схема цифровой подписи Эль-Гамаля // Управление ключами шифрования и безопасность сети / Пер. А. Н. Берлин. — Курс лекций.
Шаблон:Source

[_9096049fb2527be9-1] Elgamal, 1985.

[1]